package com.origin.niuke.dynamic;

/**
 * 连续子数组的最大和(二)
 * 算法：动态规划 + 贪心 + 双指针
 * 定义 left 和 right 存储最大和的连续子数组的首尾位置
 *
 * @author yezh
 * @date 2022/12/22 22:14
 */
public class NC166 {

    public int[] FindGreatestSumOfSubArray (int[] array) {
        int n = array.length, max = array[0], pre = array[0];
        int len = 1;
        int end = 0, maxLen = 1;
        for (int i = 1; i < n; i++) {
            ++len;
            int tmp = pre + array[i];
            // 如果加上 array[i] 后, 还比 array[i] 小, 那么直接从 array[i] 开始
            if (tmp < array[i]) {
                len = 1;
                pre = array[i];
            } else pre = tmp;
            // 当前的最大和与最大值比较
            if (pre > max || pre == max && len > maxLen) {
                max = pre;
                end = i;
                maxLen = len;
            }
        }
        int[] ans = new int[maxLen];
        int start = end - maxLen + 1;
        for (int i = start; i <= end; i++) ans[i - start] = array[i];
        return ans;
    }

}
